#include "util.h"
#include "common_sort.h"

/*
shell sort的思想:
1.先假设[0..d-1]已经是有序的,将[d..n]的数据通过插入排序插入到[0..d-1]中
2.缩小[0..d-1]的范围

O(n) = O(n^2)

*/

void ShellSort::sort(std::vector<int>& vec) {
	int len = vec.size();

	for (int d = int(len / 2); d > 0; d /= 2) {
		for (int i = d; i < len; ++i) {
			for (int j = i; j >= d && vec[j - d] >= vec[j]; j -= d) {
				util::swap(vec, j, j - d);
			}
		}
	}
}

